% Formale Modellierung ue2
% 30 Mai 2020

# Aufgabe 1

## (a)

```sh
[FALOV]*(FALL|VOLL)[FALOV]*
```

## (b)

Ein nicht deterministischer Automat welcher Sprache *L* beschreibt findet sich in Fig.1.

![NDA for *L*](./res/1b.png)

\pagebreak

## (c)

Wenn wir Tabellenform der Zustandsübergangsfunktion $\delta$ ansehen, kommen wir auf folgende Tabelle (Tab.1):

$\delta$ | F      | A           | L           | O           | V
:--|:-:|:-:|:-:|:-:|:-:
$0$ | $\{0, 1\}$  | $\{0\}$     | $\{0\}$     | $\{0\}$     | $\{0, 4\}$
$1$ | $\emptyset$ | $\{2\}$     | $\emptyset$ | $\emptyset$ | $\emptyset$
$2$ | $\emptyset$ | $\emptyset$ | $\{3\}$     | $\emptyset$ | $\emptyset$
$3$ | $\emptyset$ | $\emptyset$ | $\{f\}$     | $\emptyset$ | $\emptyset$
$4$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\{5\}$     | $\emptyset$
$5$ | $\emptyset$ | $\emptyset$ | $\{6\}$     | $\emptyset$ | $\emptyset$
$6$ | $\emptyset$ | $\emptyset$ | $\{f\}$     | $\emptyset$ | $\emptyset$
$f$ | $\{f\}$     | $\{f\}$     | $\{f\}$     | $\{f\}$     | $\{f\}$
Table: NFA transition table

Wendet man das erlernte Verfahren an, in dem die Teilmengen zu Zuständen werden, wird iterativ folgende Tabelle errechnet (Tab.2):

$\hat\delta$  | F           | A           | L           | O           | V
:--|:-:|:-:|:-:|:-:|:-:
$\{ 0 \}$    | $\{0, 1\}$ | $\{0\}$    | $\{0\}$    | $\{0\}$    | $\{0, 4\}$
$\{ 0, 1 \}$ | $\{0, 1\}$ | $\{0, 2\}$ | $\{0\}$    | $\{0, 5\}$ | $\{0, 4\}$
$\{ 0, 4 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0\}$    | $\{0\}$    | $\{0, 4\}$
$\{ 0, 2 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, 3\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 5 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, 6\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 3 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, f\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 6 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, f\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, f \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 1 \}$ | $\{0, 1, f\}$ | $\{0, 2, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 4 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, 5, f\}$ | $\{0, 4, f\}$
$\{ 0, 2 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, 3, f\}$ | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 5 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, 6, f\}$ | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 3 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 6 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
Table: DFA transition table draft

Werden die neuen Zustände sortiert, ergibt sich die folgende Tabellenform der neuen Zustandsübergangsfunktion $\hat\delta$ (Tab.3):

\pagebreak

$\hat\delta$  | F           | A           | L           | O           | V
:--|:-:|:-:|:-:|:-:|:-:
$\{ 0 \}$    | $\{0, 1\}$ | $\{0\}$    | $\{0\}$    | $\{0\}$    | $\{0, 4\}$
$\{ 0, 1 \}$ | $\{0, 1\}$ | $\{0, 2\}$ | $\{0\}$    | $\{0, 5\}$ | $\{0, 4\}$
$\{ 0, 2 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, 3\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 3 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, f\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 4 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0\}$    | $\{0\}$    | $\{0, 4\}$
$\{ 0, 5 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, 6\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, 6 \}$ | $\{0, 1\}$ | $\{0\}$    | $\{0, f\}$ | $\{0\}$    | $\{0, 4\}$
$\{ 0, f \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 1 \}$ | $\{0, 1, f\}$ | $\{0, 2, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 2 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, 3, f\}$ | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 3 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 4 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, 5, f\}$ | $\{0, 4, f\}$
$\{ 0, 5 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, 6, f\}$ | $\{0, f\}$    | $\{0, 4, f\}$
$\{ 0, 6 \}$ | $\{0, 1, f\}$ | $\{0, f\}$    | $\{0, f\}$    | $\{0, f\}$    | $\{0, 4, f\}$
Table: DFA transition table final

# Aufgabe 2

## (a)

Der Ausdruck $(a+(ba)^+)c^*$ ergibt beispielsweise einen NFA wie abgebildet in Fig.2:

![NFA für $(a+(ba)^+)c^*$](./res/2a.png)

## (b)

Der Ausdruck $aba^+(a+b)^*$ ergibt beispielsweise einen NFA wie abgebildet in Fig.3:

![NFA für $aba^+(a+b)^*$](./res/2b.png)

# Aufgabe 3

Wir beginnen mit folgendem gegebenen Automaten.

![](./res/3x-0.png)\

Initiell können wir neue formelle Start- und Endzustände *i, f* einführen.

*Hinweis: Zustand 2 sollte eigentlich nach Einführen des neuen Endzustandes f kein Endzustand mehr sein. Meine Grafiken sind iterativ entstanden und es wäre ein Aufwand, diese zu rekonstruieren, bitte um Verzeihung :(. *

![](./res/3x-1.png)\

Als nächstes führen wir alternative Zustansübergänge ein um uns auf Elimination von Zustand *0* vorzubereiten. Anschließend eliminieren wir auch Zustand *0*.

![](./res/3x-2.png)\
![](./res/3x-3.png)\

Weil an dieser Stelle noch so viele Zustandsübergänge von Zustand *2* ausgehen, nehmen wir uns vor, diesen als nächstes zu eliminieren und führen auch dafür neue Zustandsübergänge ein. Anschließend wird auch der Zustand *2* eliminiert.

*Hinweis: Da es vielleicht schwer zu erkennen ist, der neue Zustandsübergang soll folgender sein:* $(a^+b^*)^+$

![](./res/3x-4.png)\
![](./res/3x-5.png)\

Zu guter Letzt bleibt uns nur noch Zustand *1*, für welchen wir wie bisher vorgehen.

![](./res/3x-6.png)\
![](./res/3x-7.png)\

Aus dem Endergebnis lesen wir ab, dass der reguläre Ausdruck

$$ (a + \varepsilon)(b(a+\varepsilon)))^*(a^+b^*)^+ $$

ein Ausdruck sein muss, dessen Sprache äquivalent ist zu der unseres ursprünglichen Automaten.

\pagebreak

# Aufgabe 4

## (a)

Noch zur Notation, um Symbole von Meta Symbolen zu unterscheiden, werden Symbole die nicht ein Teil der Meta Symbole sind `durch anschreiben in einem monospace font` gekennzeichnet.

||
--:|--:|:--
$space =$     | $s=$   | $\{$`␣`$\}$
$num =$       | $N=$   | $\{$`1`$, ...,$`9`$\}\{$`0`$, ...,$`9`$\}^*$
$romnum =$    | $R=$   | $($`i`$+$`v`$+$`x`$)^+$
$lowercase =$ | $l=$   | $\{$`a`$, ...,$`z`$\}$
$uppercase =$ | $u=$   | $\{$`A`$, ...,$`Z`$\}$
$lcword =$    | $W_1=$ | $l^+$
$word =$      | $W_2=$ | $(l \cup u)^+$
$para =$      | $P=$   | $§N + §§Ns$`f`$($`f`$+ \varepsilon)$`.`
$sublitera$   | $Q=$   | `sublit`$sR$
$litera$      | $L=$   | `lit`$sW_1 (sQ + \varepsilon)$
$digit$       | $D=$   | `Z`$sN$
$paragraph =$ |        | $Ps$`Abs.`$sNs(L+D)sW_2$

*Hinweis: Es wurde versucht, hier auf die best practices zu achten, aber aufgrund der vielen *`␣` *Zeichen ist das Ergebnis nicht sehr leserlich geworden.*

## (b)

Eine *POSIX compliant extended regular expression (ERE)* die sich ensetzen ließe wäre:

```sh
^(§[1-9][0-9]*|§§[1-9][0-9]* ff?\.) Abs. [1-9][0-9]*
 (lit [a-z]( sublit [ivx]+)?|Z [1-9][0-9]*) [a-zA-Z]+$
```

Zwar werden *ERE* typischerweise ganz ausgeschrieben, aber zur verbesserten Lesbarkeit wird derselbe Ausdruck in Module zerlegt. Dabei bezeichne `:=` die Zuweisung eines solchen Moduls. Um Module, welcher zur Meta Sprache gehören, nicht zu verwechseln, führen wir die Notation `\module` ein für die Verwendung eines derartigen Moduls der Meta Sprache. Zwar ist das nicht komplett konsistent mit dem Standard (z.B. bezeichnet `\.` immer noch einen escape character), aber es reicht für unsere Zwecke aus.

```sh
num       := [1-9][0-9]*
word      := [a-zA-Z]+
lowercase := [a-z]+
romnum    := [ivx]+

para      := (§\num|§§\num ff?\.)

sublitera := sublit \romnum
litera    := lit \lowercase( \sublitera)?
digit     := Z \num

paragraph := ^\para Abs. \num (\litera|\digit) \word$
```

## (c)

Die Syntaxdiagramme der einzelnen Symbole aus *4a* finden sich in folgender Abbildung (Fig.4).

![Syntaxdiagramme](./res/4c-drawio.png)

# Aufgabe 5

## (a)

|$((\{ a, ab \} \cup \{ \varepsilon \}) \cdot (\{ \varepsilon, bb, cc \} \cup \{b\})) \cup \{ a, c\}$|
|:--|
|$(\{ a, ab, \varepsilon \} \cdot \{ \varepsilon, b, bb, cc \}) \cup \{ a, c\}$|
|$\{ a, ab, b, bb, cc, \varepsilon, abb, acc, abbb, abcc \} \cup \{ a, c\}$|
|$\{ \varepsilon, a, b, c, ab, abb, acc, abbb, abcc, bb, cc \}$|
|$\{ a, b, c, ab, abb, acc, abbb, abcc, bb, cc \}^*$|

## (b)

|$\{a\}^* \cdot (\{a\} \cup \{ \varepsilon \})$|
|:--|
|$\{a\}^* \cdot \{a, \varepsilon\}$|
|$\{a\}^*$|

## (c)

|$(\{b\}^* \cdot \{b\}^+) \cdot \{b\}^*$|
|:--|
|$\{b\}^*  \cdot \{b\}^* \cdot \{b\}^+ \cdot \{b\}^*$|
|$\{b\}^+$|

## (d)

|$\{ac,b,aba\} \cdot \{\}$|
|:--|
|$\{\}$|

## (e)

|$\{ad,bc,ab\} \cup \{\}^*$|
|:--|
|$\{ad,bc,ab\} \cup \{\varepsilon\}$|
|$\{ad,bc,ab,\varepsilon\}$|
|$\{ad,bc,ab\}^*$|

# Aufgabe 6

## (a)

$L_1 \cdot L_2 = L_2 \cdot L_1$ gilt allgemein nicht, wie durch Gegenbeispiel $\{a\} \cdot \{b\} \not = \{b\} \cdot \{a\}$ gezeigt werden kann.

## (b)

$L_1^* \cdot \{\varepsilon\} = \{\}$ kann *nie* gelten, da $L_1^* \cdot \{\varepsilon\} = L_1^* = L_1 \cup \{\varepsilon\} \not = \{\}$. Sogar $L_1 = \{\}$ ist ein gültiges Gegenbeispiel.

## (c)

$\varepsilon \in L_1 \cdot L_2$ *genau dann wenn* $\varepsilon \in L_1$ *und* $\varepsilon \in L_2$ stimmt, wie aus der Regel $\varepsilon \cdot A = A \cdot \varepsilon = A$ folgt. *A* muss Wert $\varepsilon$ annehmen. Dass als Ergebniss einer Konkatenation $\varepsilon$ in $L_1 \cdot L_2$ enthalten ist, kann also nur geschehen, wenn $\varepsilon$ in beiden Sprachen enthalten ist.

## (d)

*Ist* $L_1$ *regulär, so ist jede Sprache* $L \subseteq L_1$ *auch regulär*. stimmt, da jede reguläre Sprache auch als Zusammensetzung kleiner regulären Sprachen betrachtet werden können. Ist $L$ eines der Sprachen $\{\}, \{\varepsilon\},\{s\}; s \in \Sigma$, so ist $L$ bereits eine reguläre Sprache. Ansonsten kann $L$ aus diesen regulären Sprachen aufgebaut werden.

## (e)

*Ist die Menge* $L_1$ *endlich, so ist* $L_1$ *regulär* stimmt. Das Problem dass viele kontextfreie Grammatiken davon abhält, regulär zu sein, ist deren *potenziell* unendlicher "Speicher" den sie benötigen. Ist dieser Speicher begrenzt, so kann eine Sprache ausführlich genug spezifiziert werden um mit $L_1$ äquivalent zu sein. Eine alternative Betrachtungsweise ist, dass ein endlicher Automat mit $2^{|L_1|}$ Zuständen ausgestattet werden kann und konstruiert werden kann, um jede mögliche Eingabe abzudecken.

# Aufgabe 7

Gegeben ist eine Grammatik $G = \langle N, T, P, A \rangle$.

## (a)

Liegt `halleleluuja.` in der Sprache $\mathcal{L}(G)$?

|"halleleluuja."|
|:-:|
|B "."|
|"hal" C "ja."|
|"halle" C "ja."|
|"hallele" C "ja."|
|"hallelel" D "ja."|
|"hallelelu" D "ja."|
|"halleleluuja."|

Da `halleleluuja.` konstruiert werden kann liegt es in der Sprache.

## (b)

Liegt `hallelu` in der Sprache $\mathcal{L}(G)$?

Es kann nicht in der Sprache liegen, da das einzige Gesetz, mit dem sich ein Wort welches mit `hal` anfängt konstruieren lässt, die falsche Endsequenz ergibt. Wendet man $B \in P$ an, so endet ein Wort immer mit `ja`. Wendet man allerdings $B \in P$ nicht an, so kann das Wort nicht mit `hal` beginnen.

## (c)

Richtig! Da jedes Wort mit Symbol $A \in P$ beginnt und folglich auch ein Symbol $B \in P$ beinhält, muss es zumindest ein `l` beinhalten. Da aber bei beiden Optionen des später entstehenden Symbols $C \in P$ auch ein `l` vorkommt, muss jedes Wort der Sprache zumindest zwei `l` beinhalten.

## (d)

Auch richtig! Nämlich enthält jedes Wort Symbol $B \in P$, wodurch zumindest ein `ja` enthalten sein muss.

## (e)

Das kürzeste Wort besteht aus küzrsten Symbolen ausgehend von Startsymbol, daher `halluja.`

## (f)

Endliche Automaten sind äquivalent einer regulären Sprache. Das bedeutet, jede reguläre Sprache lässt sich in einen endlichen Automaten übersetzen und umgekehrt. Daraus folgt, das ein endlicher Automat nur so ausdrucksstark wie eine reguläre Sprache ist.

Reguläre Sprachen sind in der Chomsky-Hierarchie unter den kontextfreien Grammatiken und daher lassen sich nicht alle Sprachen welche durch kontextfreien Grammatiken spezifiziert werden können durch reguläre Sprachen abbilden. Das bedeutet in Folge für uns, dass wir womöglich keinen derartigen Automaten finden werden können.

In diesem Fall lässt sich auch keiner finden, das Problem sind nämlich Konkatenationen von Terminal und Nicht-Terminal Symbolen wie etwa bei Symbol $B \in P$. Um dieses Bildungsgesetzt einzuhalten, müssten wir uns "merken", wir oft der anschließende Teil `ja` noch zu konkatenieren wäre, was unsere Automaten leider nicht können.

# Aufgabe 8

## (a)

Zur erweiterten Lesbarkeit stelle $\diamond$ ein Leerzeichen dar.

$$ G = \langle N, T, P, E \rangle $$
$$ N = \{ Expr, Formula, Real, Int, Symbol, Digit, Digits \} $$
$$ T = \{ 0, 1, ..., 9, +, -, *, :, =, \diamond \} $$

Weiters sei P die Menge folgender Bildungsgesetze:

||
|:--|
|$Expr \to Formula[$`"`$\diamond$`="`$]$|
|$Formula \to Real$`"`$\diamond$`"`$Symbol$`"`$\diamond$`"`$Real$|
|$Real \to [$`"-"`$] Int \mid$`"0"`|
|$Int \to Digit \{Digits\}$|
|$Digit \to$`"1"`$\mid ... \mid$`"9"`|
|$Digits \to$`"0"`$\mid ... \mid$`"9"`|
|$Symbol \to$`"+"`$\mid$`"-"`$\mid$`"*"`$\mid$`":"`|

Die Sprache $\mathcal{R}$ ist gleichzeitig eine reguläre Sprache, weil keines der problematischen Bildungsgesetze vorkommen, in welchen Terminale von Non-Terminalen umgeben sind. Beispielsweise ließe sich mit hilfe einer ERE folgender regulärer Ausdruck verwenden:

```sh
extended regular expression:
(\-?[1-9][0-9]*|0) [\+\-\*\:] (\-?[1-9][0-9]*|0) =
```

## (b)

Es wird gleich vorgegangen wie bereits in (a).

$$ G = \langle N, T, P, E \rangle $$
$$ N = \{ Expr, Formula, FTail, Real, Int, Symbol, Digit, Digits \} $$
$$ T = \{ 0, 1, ..., 9, +, -, *, :, =, \diamond \} $$

||
|:--|
|$Expr \to Formula[$`"`$\diamond$`="`$]$|
|$Formula \to Real$`"`$\diamond$`"`$Symbol$`"`$\diamond$`"`$Real \{FTail\}$|
|$FTail \to Symbol$`"`$\diamond$`"`$Real$|
|$Real \to [$`"-"`$] Int \mid$`"0"`|
|$Int \to Digit \{Digits\}$|
|$Digit \to$`"1"`$\mid ... \mid$`"9"`|
|$Digits \to$`"0"`$\mid ... \mid$`"9"`|
|$Symbol \to$`"+"`$\mid$`"-"`$\mid$`"*"`$\mid$`":"`|

Wie sich erkennen lässt, hat sich die Grammatik um Sprache $\mathcal{R}'$ abzubilden nur im Bildungsgesetz für die Formel $Formula$ geändert. Nämlich lässt diese jetzt optional mehrere "Formelrümpfe" ($FTail$) zu. Weil das einer zusätzlichen "0 oder mehr" Regel entspricht, lässt sich gleichzeitig auch der reguläre Ausruck aus (a) erweitern. Somit handelt es sich auch bei $\mathcal{R}'$ um eine reguläre Sprache.

```sh
extended regular expression:
((\-?[1-9][0-9]*|0) [\+\-\*\:] )+(\-?[1-9][0-9]*|0) =
```

## (c)

Es wird gleich vorgegangen wie bereits in (a).

$$ G = \langle N, T, P, E \rangle $$
$$ N = \{ Expr, Formula, FTail, Term, Real, Int, Symbol, Digit, Digits \} $$
$$ T = \{ 0, 1, ..., 9, +, -, *, :, =, (, ), \diamond \} $$

||
|:--|
|$Expr \to Formula[$`"`$\diamond$`="`$]$|
|$Formula \to Term$`"`$\diamond$`"`$Symbol$`"`$\diamond$`"`$Term \{FTail\}$|
|$FTail \to Symbol$`"`$\diamond$`"`$Term$|
|$Term \to Real \mid$`"("`$Formula$`")"`|
|$Real \to [$`"-"`$] Int \mid$`"0"`|
|$Int \to Digit \{Digits\}$|
|$Digit \to$`"1"`$\mid ... \mid$`"9"`|
|$Digits \to$`"0"`$\mid ... \mid$`"9"`|
|$Symbol \to$`"+"`$\mid$`"-"`$\mid$`"*"`$\mid$`":"`|

*Hinweis: Es ist bewusst nicht zugelassen worden, dass der äußerste Ausdruck* (ein Bsp. wäre $(123 + 312)$) *geklammert wird, weil es aus der Angabe auch nicht hervorgeht. Glücklicherweise wäre das keine allzu aufwendige Änderung.*

Bei der durch diese Grammatik spezifizierten Sprache $\mathcal{R}''$ handelt es sich nicht mehr um eine reguläre Sprache! Die komplexe Relation Zwischen $F_1$ und $A$ lässt sich nicht mehr so einfach als Wiederholungsregel oder sonstiges darstellen. Um einen korrekten Ausdruck erstellen zu können, muss "zwischengespeichert" werden, dass es sich um einen geklammerten Ausdruck handelt. Da diese Rekursion beliebig tief gehen kann, ist sie daher nicht beschränkt und wir können auch keinen endlichen Automaten zur Modellierung dafür verwenden.

# Aufgabe 9

*Hinweis: In diesen Beispielen ist das Universum $\mathcal{U}$ so gewählt, dass Elemente dessen nicht zwingend Frösche sind. Diese Annahme wäre aber in Retrospekt für Unteraufgaben (b) bis (e) hilfreich gewesen.*

## (a)

sei $\mathcal{P} = \{ quaxi\_ist\_frosch/0 \}$, dann

$quaxi\_ist\_frosch$

## (b)

sei $\mathcal{P} = \{ Ist\_Grün/1, Frosch/1 \}$, dann

$\forall x (Frosch(x) \supset Ist\_Grün(x))$

## (c)

sei $\mathcal{P} = \{ Frosch/1, Frisst\_Fliegen/1 \}$, dann

$\exists x (Frosch(x) \land Frisst\_Fliegen(x))$

## (d)

sei $\mathcal{P} = \{ Ist\_Grün/1, Frosch/1, Frisst\_Fliegen/1 \}$, dann

$\forall x ((Ist\_Grün(x) \land Frosch(x)) \supset Frisst\_Fliegen(x))$

## (e)

sei $\mathcal{P} = \{ Frosch/1, Kann\_Fliegen/1, Frisst\_Spinnen/1 \}$, dann

$\exists x (Frosch(x) \land (Kann\_Fliegen(x) \land \neg Frisst\_Spinnen(x)))$

# Aufgabe 10

## (a)

$\exists x (Lustig(x) \supset SchautAn(x, teletubbies) \equiv SchautAn(x, spongebob))$

## (b)

$\exists x \forall y ((Lustig(x) \land Sendung(x)) \supset SchautAn(y, x))$

## (c)

"Alle sind Kinder und schauen *Heidi*."

Das würde zwar stimmen, wären alle Kinder, da alle Kinder tatsächlich Heidi schauen, aber es gibt auch x die Sendungen sind im Universum $\mathcal{U}$.

## (d)

"Alle Sendungen die lustig sind werden von zumindest einem Kind geschaut."

Das ist wahr, weil folgende Tupeln in der Interpretation I(SchautAn) enthalten sind: $(Karo, Spongebob), (Anna, Teletubbies), (Anna, Barbapapas)$.

## (e)

"Alle schauen entweder *Heidi*, oder *Niklas*, aber nicht beide gleichzeitig."

Zur Überprüfung müsste man vergleichen, überall wo jemand *Heidi* schaut, darf kein Tupel existieren in dem *Niklas* geschaut wird. Schnell lässt sich erkennen, dass jeweils *Tom, Flo, Anna* und *Karo* *Heidi* schauen. Da niemand gleichzeitig *Niklas* schaut, ist die Aussage wahr.

# Aufgabe 11

## (a)

Bevor Wörter für das gegebene Petri-Netz von unserem Automaten abgelesen werden können, noch bevor wir unseren Automaten überhaupt aufbauen, müssen wir uns sicher sein, wie alle Abläufe des Petri-Netzes aussehen. Wird bei Transition $t_2$ eine Marke konsumiert, so duplizieren wir die Marken an Stelle $s_1$, was einen unendlich anwachsenden Automaten erzeugen würde. Wird genau auf die Angabe geschaut, so fällt eine "2" bei dem Eingang der Transition $t_2$ auf, sodass immer *2* Marken konsumiert werden. An dieser Stelle wird jetzt einfach iterativ probiert und ein Automat aufgebaut.

Zur Notation des Automaten, wir spezifizieren das Alphabet $\Sigma = \{ t_1, ..., t_4 \}$ und die Zustände $Q = \{ m_1 m_2 m_3 m_4 \}, m_x \in [0, 2]$. Dabei beschreibt eine Ziffer $m_x$ eines Zustandes immer die Anzahl an Marken die sich an Stelle $s_x$ befinden mit $x \in [1, 4]$. Dadurch können wir bereits abschätzen, wieviele Zustände maximal auftreten könnten, nämlich gibt es 3 Möglichkeiten pro Stelle.

Bauen wir schlussendlich den Automaten auf, so sehen wir, dass bei weitem nicht alle Möglichkeiten ins Spiel kommen (Fig.5).

![DFA describing Petri Net words](./res/11x.png)

Es fällt auch auf, dass Zustand *2001* als Endzustand designiert wurde. Theoretisch wäre jeder Zustand ein Endzustand, würden wir zulassen, das keine Transitionen mehr durchgeführt werden, bevor noch im Automaten der Endzustand erreicht würde. Aber die Wörter die dadurch entstehen, wenn wir zulassen, dass der Automat vor Erreichen von Zustand *2001* stoppt, sind *Teilmengen* jener dieser Variante. Das Vereinfacht auch den nächsten Schritt.

Mithilfe dieses Automaten *A* können wir nun einen regulären Ausdruck erstellen der die Sprache $\mathcal{L}(A)$ des Automaten spezifiziert. Diese Sprache ist nun gleichzeitig die Menge aller Wörter die gültige Abfolgen der Transitionsänderungen beschreiben.

Damit kein unnötig komplexer Ausdruck entsteht, legen wir auch fest, dass sobald Zustand *2001* mithilfe des Überganges $t_2$ erreicht wird, dieser Übergang kein weiteres Mal traversiert wird. Wäre das wichtig, dann ließen sich alle Wörter durch die folgende Entstehende Sprache einfach verketten um auf dieses Ergebnis zu kommen.

Mit all diesen Simplifikationen finden wir schnell einen regulären Ausdruck für die Sprache des Automaten (als ERE):

```sh
^((t1)*((t2)((t3)(t1)*(t4)|(t4)(t1)*(t3))?)?)$
```

Dieser Ausdruck sieht sehr kompliziert aus, aber nur wegen der vielen notwendigen Klammern für die einzelnen Übergänge $t_x$. Wenn die Übergänge nicht als $t_x, x \in [1, 4]$ definiert werden, sondern nur als $x$, bekommen wir einen vereinfachten und hoffentlich viel leserlichen Ausdruck:

```sh
^(1*(2(31*4|41*3)?)?)$
```

Die Sprache also kann beispielsweise folgende Gestalten annehmen:

```
t1...t1t2t3t1...t1t4
t1...t1t2t4t1...t1t3
```

Wobei die `...` nur beliebig ofte Wiederholungen von `t1` angeben.

## (b)

Für manche Petri-Netze lässt sich keine endliche Menge an Zuständen für die Verteilung der Markierungen finden. Weil diese Möglichkeiten der Markenverteilung nicht *beschränkt* sind, wachsen die möglichen Zustände ins Unendliche. Das hält uns auch davon ab, einen *endlichen* Automaten, der macht was wir bereits in (a) gemacht haben zu finden.

Ein sehr naheliegendes Beispiel ist der Automat aus (a) mit einer minimalen Veränderung. Wird nämlich der Übergang durch Transition $t_2$ so definiert, dass nicht *2* Marken konsumiert werden, sondern nur eine, stoßen wir auf dieses Problem.

Versuchen wir bei diesem neuen Automaten dasselbe Schema wie bereits in (a) anzuwenden und einen Automaten iterativ aufzubauen, so passieren interessante Sachen. Aus (a) konnten wir observieren, dass die totale Menge an Marken $m_1 + m_2 + m_3 + m_4 \leq 3$ sein musste. Daher, es war uns nicht möglich, Marken zu *duplizieren*. Somit haben die Transitionen einen wiederkehrenden Zyklus gebildet, den wir abbilden konnten. Wenn aber Duplizierung schon erlaubt ist, dann wächst die Menge der Marken bis ins Unendliche. In Fig.6 findet sich ein solcher Aufbauversuch.

![DFA NOT describing Petri Net words](./res/11b.png)

Wie schnell ersichtlich ist, kommen viele neue Zustände dazu. Wo früher unser automat bei *3001* wieder an den Startzustand zurückgekehrt wäre, gibt es hier plötzlich neue Möglichkeiten, weil $m_1$ um *1* größer ist als zuvor. Das ist natürlich kein vollständiger Automat, die Zustände *....* sollten jeweils die restlichen Segmente des Automaten beschreiben, wobei diese nicht endlich sein können.

# Aufgabe 12

Ein Petri Netz welches den Ablauf mit initiellen Bedingungen modelliert findet sich in Fig.7.

![Petri Net fastfood process](./res/12x.png){ width=115% }

Bei dieser Aufgabe zentral ist das verschiedene Stellen des Restaurants nur abgearbeitet können, wenn ein Mitarbeiter zur Verfügung steht. Ein Mitarbeiter stellt somit die zentrale Ressource dar und kann auch beliebig tätig werden. Das führt in Folge, dass viele Transitionen nur durchgeführt werden können, wenn ein Mitarbeiter tätig wird. Dieser Vorgang ist modelliert mithilfe einer Transition *"busy"*, an welcher ein Mitarbeiter von der "empl.-free" (verfügbar) Stelle in die "empl.-busy" (beschäftigt) Stelle transitioniert. Wird ein Mitarbeiter fertig, so kommt er in die Stelle "empl.-done" (fertig), wo die Mitarbeiter wieder in "empl.-free" transitionieren können.

Die nächste elementare Observation sind die vielen Stellen, an welchen jeweils eine einzige Person darauf warten kann, bedient zu werden. All diese Stellen sind klassische Engpässe, an denen der Durchfluss begrenzt werden muss. Diese Strukturen finden sich beispielsweise an Stellen "counter-order", "terminal", "counter-take", "drive-thru-order", "drive-thru-pay" und "drive-thru-take". Für all diese Stellen gilt, dass sie eine zusätzliche Stelle "\*-buffer" haben, welche sie auf höchstens *1* Marke zu jedem Zeitpunkt beschränkt.

Ein wichtiges Detail ist hier, dass überall wo Buffer vorkommen, und die zuständige "\*-buffer" zu "\*" Transition nur einen Eingang hat, müssen an Stelle "\*" jeweils *2* Marken konsumiert werden. Diese Konstellation ergibt sich nur an Stelle "count-order" sowie "terminal" und die darauffolgenden Transitionen *"order"*.

*Hinweis: Das verwendete Werkzeug hatte Bugs und konnte Mehrfachkonsum von Marken nicht richtig darstellen, daher wird das hier explizit erwähnt.*

Als nächstes interessant sind die Zusammenspiele dieser drei Systeme, dem *drive-thru* Mechanismus, dem *order* Mechanismus und dem *employee* Mechanismus. Überall wo Mitarbeiter tätig werden müssen, stellen sie ein bottleneck für den weiteren Durchgang der anderen zwei Systeme dar. Mitarbeiter können nicht im selben Schritt, in dem sie tätig werden, wieder frei werden, deswegen können sie erst bei der darauffolgenden Transition befreit werden. Aus diesem Grund wurden auch zusätzliche Transitionen *begone* für die Mechanismen *drive-thru* und *order* erstellt, obwohl an Stellen "drive-thru-end" und "counter-end" die Kunden bereits fertig wären.
